/**
 * Created by L.jp
 * Description:有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，
 * 变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
 * 示例1
 * 输入：
 * [3,4,5,1,2]
 * 返回值：
 * 1
 * User: 86189
 * Date: 2021-12-13
 * Time: 15:43
 */
//采用二分法查找数组的最小值，因为输入的数组时经过旋转的，而且是非递减序列，肯定会以某个中间值构成两部分，每一部分都还是非递减的
//那么我们就可以采用这一个性质来做这个题目，先定义左边指针left=0和右边指针right=len-1,再找到中间值mid=(left+right)/2,如果
//mid的值会大于right的值，那么说明最小值在mid的右边部分，并且最小值不会是mid的值，也就是left=mid+1（因为mid的值如果是最小的话就不可能会大于right的值）
//如果mid的值小于right的值，那么说明最小值在mid的左边部分，因为要找最小值，那么mid也有可能是最小值，所以right=mid
//如果有重复的值也就是mid的值会等于right的值，那么无论right的值是不是最小值，他总有一个替代值就是mid的值，因此就可以缩小范围
// 忽略右端点，让right--;当left，mid,right相遇时，就找到了最小值，返回left的值即可
public class Solution {
    public static  int minArray(int[] array) {
        if (array==null || array.length==0){
            return 0;
        }
        int left=0;
        int right=array.length-1;
        int mid=0;
        while(left<right){
            mid=(left+right)/2;
            if(array[mid]<array[right]){//中间值小于右端点的值，那么最小值就在mid的左边部分，mid也可能是最小值
                right=mid;
            }else if(array[mid]>array[right]) {//
                left=mid+1;
            }else{
                right=right-1;
            }
        }
        return array[left];
    }
    public static void main(String[] args) {
       //int[] array={3,4,5,1,2};
       int[] array={3,4,4,1,1};
       //int[] array={0,0,1,1,1};
        System.out.println("最小值是："+minArray(array));

    }
}
